#ifndef GRAPH_H
#define GRAPH_H

#include <QVector>
#include <QString>
#include <queue>
#include <limits>

struct Edge {
    int to;
    double timeSec;
};

class Graph {
public:
    Graph(int n = 0) { resize(n); }

    void resize(int n) {
        adj.clear();
        adj.resize(n);
        names.clear();
        names.resize(n);
    }

    int size() const { return adj.size(); }

    void setName(int i, const QString &name) {
        if (i>=0 && i<size()) names[i] = name;
    }

    QString name(int i) const {
        return (i>=0 && i<size()) ? names[i] : QString();
    }

    void addUndirectedEdge(int u, int v, double timeSec) {
        if (u<0||v<0||u>=size()||v>=size()) return;
        adj[u].append({v, timeSec});
        adj[v].append({u, timeSec});
    }

    // Dijkstra：返回 (总时间, 路径顶点序列)
    std::pair<double, QVector<int>> shortestTimePath(int s, int t) const {
        const double INF = std::numeric_limits<double>::infinity();
        int n = size();
        QVector<double> dist(n, INF);
        QVector<int> prev(n, -1);

        using Node = QPair<double,int>; // (dist, node)
        auto cmp = [](const Node &a, const Node &b){ return a.first > b.first; };
        std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);

        dist[s] = 0.0;
        pq.push(qMakePair(0.0, s));  // 使用 qMakePair 代替花括号

        while(!pq.empty()){
            // 移除结构化绑定，改用传统方式
            Node node = pq.top();
            pq.pop();
            double d = node.first;
            int u = node.second;

            if (d > dist[u]) continue;
            if (u == t) break; // 已找到最短
            for (const auto &e : adj[u]){
                double nd = d + e.timeSec;
                if (nd < dist[e.to]){
                    dist[e.to] = nd;
                    prev[e.to] = u;
                    pq.push(qMakePair(nd, e.to));  // 使用 qMakePair 代替花括号
                }
            }
        }

        QVector<int> path;
        if (dist[t] == INF) return std::make_pair(INF, path);

        for (int at = t; at != -1; at = prev[at]) {
              path.prepend(at);
          }
        return std::make_pair(dist[t], path);
    }

private:
    struct Edge {
        int to;
        double timeSec;
    };
    QVector<QVector<Edge>> adj;
    QVector<QString> names;
};

#endif // GRAPH_H
